package leecode.stringAndArray.String;

public class KMP {
    public static void main(String[] args) {
        /*测试next数组
        int[] ints = next(new char[]{'a','b','c','d','a','b','c','e'});
        for (int a: ints) {
            System.out.println(a);
        }*/
    int index = kmp("aaaaa","bba");
        System.out.println(index);


    }

    public static int kmp(String haystack, String needle){
        if(needle.equals("")){
            return 0;
        }
        int[] next = next(needle.toCharArray());

        int i=0,j=0;
        while (i<haystack.length() && j<needle.length()){
            //j有时会因为next[j]而回到-1，这说明原字符中和模式串匹配不成功的坏字符，在模式串之前也没有出现过，于是i和j都++
            if(j==-1 || haystack.charAt(i)==needle.charAt(j)){
                i++;
                j++;
            }else{
                j=next[j];
            }
        }
        //如果j到了neddle的最后一个元素，表示匹配成功，返回位置
        if(j==needle.length()){
            return i-j;
        }else {
            return -1;
        }
    }

    /*递推，当知道next[j]=k时，求next[j+1]*/
    public static int[] next(char[] chars){
        //创建需要返回的next数组
        int[] next = new int[chars.length];
        //第一个字母没有前缀，所以next[0]设为-1
        // 第二个字母的前面只有一个字母，所以不存在公共前后缀，next[1]为0
        int k=-1,j=0;
        next[j]=k;

        while (j<chars.length-1){
            //当chars[k] = chars[i] 继续匹配
            if(k==-1 ||chars[k]==chars[j]){
                j++;
                k++;
                next[j]=k;
            }else{
                //这里详见https://blog.csdn.net/yyzsir/article/details/89462339
                k=next[k];
            }
        }

        return next;
    }


}
